package src.CodeTop;

/**
 * 存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。
 *
 * 返回同样按升序排列的结果链表。
 *
 *  
 *
 * 示例 1：
 *
 *
 * 输入：head = [1,2,3,3,4,4,5]
 * 输出：[1,2,5]
 * 示例 2：
 *
 *
 * 输入：head = [1,1,1,2,3]
 * 输出：[2,3]
 *
 */

public class _82RemoveDuplicatesFromSortedListII {
    public static void main(String[] args) {

    }

    public ListNode deleteDuplicates(ListNode head) {
        // 校验合法性
        if (head == null)
            return head;
        // 定义虚拟头结点，因为可能会删除第一个元素
        ListNode virNode = new ListNode(0);
        // 连接到原链表
        virNode.next = head;
        // 定义快慢指针，两指针相差一个结点
        ListNode fast = head, slow = virNode;
        while (fast != null && fast.next != null) {
            // 如果两结点的值不相等，则继续向下移动
            if (fast.next.val != slow.next.val) {
                fast = fast.next;
                slow = slow.next;
            }else {
                // 如果两结点的值相等，则快指针后移，直到不相等
                while (fast != null && fast.next != null && fast.next.val == slow.next.val) {
                    fast = fast.next;
                }
                // 将慢指针的下一个结点指到快指针的下一个结点后面
                slow.next = fast.next;
                // 快指针后移
                fast = fast.next;
            }
        }
        return virNode.next;
    }
}
